{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Scramble String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isScramble"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #扰乱字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "使用下面描述的算法可以扰乱字符串 <code>s</code> 得到字符串 <code>t</code> ：\n",
    "<ol>\n",
    "\t<li>如果字符串的长度为 1 ，算法停止</li>\n",
    "\t<li>如果字符串的长度 > 1 ，执行下述步骤：\n",
    "\t<ul>\n",
    "\t\t<li>在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 <code>s</code> ，则可以将其分成两个子字符串 <code>x</code> 和 <code>y</code> ，且满足 <code>s = x + y</code> 。</li>\n",
    "\t\t<li><strong>随机</strong> 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，<code>s</code> 可能是 <code>s = x + y</code> 或者 <code>s = y + x</code> 。</li>\n",
    "\t\t<li>在 <code>x</code> 和 <code>y</code> 这两个子字符串上继续从步骤 1 开始递归执行此算法。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ol>\n",
    "\n",
    "<p>给你两个 <strong>长度相等</strong> 的字符串 <code>s1</code><em> </em>和 <code>s2</code>，判断 <code>s2</code><em> </em>是否是 <code>s1</code><em> </em>的扰乱字符串。如果是，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"great\", s2 = \"rgeat\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>s1 上可能发生的一种情形是：\n",
    "\"great\" --> \"gr/eat\" // 在一个随机下标处分割得到两个子字符串\n",
    "\"gr/eat\" --> \"gr/eat\" // 随机决定：「保持这两个子字符串的顺序不变」\n",
    "\"gr/eat\" --> \"g/r / e/at\" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割\n",
    "\"g/r / e/at\" --> \"r/g / e/at\" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」\n",
    "\"r/g / e/at\" --> \"r/g / e/ a/t\" // 继续递归执行此算法，将 \"at\" 分割得到 \"a/t\"\n",
    "\"r/g / e/ a/t\" --> \"r/g / e/ a/t\" // 随机决定：「保持这两个子字符串的顺序不变」\n",
    "算法终止，结果字符串和 s2 相同，都是 \"rgeat\"\n",
    "这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"abcde\", s2 = \"caebd\"\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"a\", s2 = \"a\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s1.length == s2.length</code></li>\n",
    "\t<li><code>1 <= s1.length <= 30</code></li>\n",
    "\t<li><code>s1</code> 和 <code>s2</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [scramble-string](https://leetcode.cn/problems/scramble-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [scramble-string](https://leetcode.cn/problems/scramble-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"great\"\\n\"rgeat\"', '\"abcde\"\\n\"caebd\"', '\"a\"\\n\"a\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def char2i(self,s):\n",
    "        return ord(s)-ord('a')\n",
    "    def compare(self, s1, s2 ):\n",
    "        dct1, dct2 = [ 0 for i in range(26)] , [ 0 for i in range(26)  ]\n",
    "        for s in s1:\n",
    "            dct1[ord(s)-ord('a')]+=1\n",
    "        for s in s2:\n",
    "            dct2[ord(s)-ord('a')]+=1\n",
    "        for i in range(26):\n",
    "            if dct1[i]!=dct2[i]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    mm=[]\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        n=len(s1)\n",
    "        if s1+s2 in self.mm:\n",
    "            return False\n",
    "        if n==1:\n",
    "            if(s1==s2 ):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        cnt1=[ 0 for i in range(26)]\n",
    "        cnt2=[ 0 for i in range(26)]\n",
    "        cnt3=[ 0 for i in range(26)]\n",
    "        for i in range(0,n-1):\n",
    "            cnt1[ self.char2i(s1[i]) ]+=1\n",
    "            cnt2[ self.char2i(s2[i]) ]+=1\n",
    "            cnt3[ self.char2i(s2[n-1-i]) ]+=1\n",
    "            if ( cnt1==cnt2):\n",
    "                if self.isScramble(s1[:i+1],s2[:i+1]) and self.isScramble(s1[i+1:],s2[i+1:]):\n",
    "                    return True\n",
    "            if ( cnt1==cnt3):\n",
    "                if self.isScramble(s1[:i+1],s2[n-1-i:]) and self.isScramble(s1[i+1:],s2[:n-1-i]):\n",
    "                    return True\n",
    "\n",
    "        self.mm.append(s1+s2)\n",
    "        self.mm.append(s2+s1)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if sorted(s1) != sorted(s2):\n",
    "            return False\n",
    "\n",
    "        memo = {}\n",
    "\n",
    "        def woo(s1, s2):\n",
    "            if (s1, s2) in memo:\n",
    "                return memo[(s1, s2)]\n",
    "\n",
    "            if s1 == s2:\n",
    "                return True\n",
    "\n",
    "            if sorted(s1) != sorted(s2):\n",
    "                return False\n",
    "\n",
    "            memo[(s1, s2)] = False\n",
    "            for i in range(1, len(s1)):\n",
    "                if woo(s1[:i], s2[:i]) and woo(s1[i:], s2[i:]) or woo(s1[:i], s2[-i:]) and woo(s1[i:], s2[:-i]):\n",
    "                    memo[(s1, s2)] = True\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return woo(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2) \n",
    "        if m != n:\n",
    "            return False \n",
    "        def eq(c1, c2):\n",
    "            arr1 = sorted([(k,v) for k,v in c1.items()])\n",
    "            arr2 = sorted([(k,v) for k,v in c1.items()])\n",
    "        @cache \n",
    "        def dfs(l1,r1, l2,r2):\n",
    "            n = r1 - l1 + 1\n",
    "            if n == 1:\n",
    "                return s1[l1] == s2[l2]\n",
    "            #print(s1[l1:r1+1])\n",
    "            for i in range(n-1):\n",
    "                a1,b1 = sorted(s1[l1:l1+i+1]), sorted(s1[l1+i+1:r1+1])\n",
    "                a2,b2 = sorted(s2[l2:l2+i+1]), sorted(s2[l2+i+1:r2+1])\n",
    "                \n",
    "                if a1 == a2 and b1 == b2:\n",
    "                    if dfs(l1,l1+i,l2,l2+i) and dfs(l1+i+1,r1,l2+i+1,r2):\n",
    "                        return True \n",
    "                a3,b3 = sorted(s2[r2-i:r2+1]), sorted(s2[l2:r2-i])\n",
    "                if a1 == a3 and b1 == b3:\n",
    "                    if dfs(l1,l1+i,r2-i,r2) and dfs(l1+i+1,r1,l2,r2-i-1):\n",
    "                        return True \n",
    "            return False \n",
    "        return dfs(0, m-1, 0, m-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        if n != len(s2):\n",
    "            return False\n",
    "\n",
    "        dp = [[[False] * (n + 1) for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                dp[i][j][1] = (s1[i]==s2[j])\n",
    "\n",
    "        for length in range(2, n + 1):\n",
    "            for i in range(n - length + 1):\n",
    "                for j in range(n - length + 1):\n",
    "                    for k in range(1, length):\n",
    "                        if (dp[i][j][k] and dp[i+k][j+k][length-k]) or \\\n",
    "                           (dp[i][j + length - k][k] and dp[i + k][j][length - k]):\n",
    "                            dp[i][j][length] = True\n",
    "                            break\n",
    "\n",
    "        return dp[0][0][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        @cache\n",
    "        def dfs(i1: int, i2: int, length: int) -> bool:\n",
    "            \"\"\"\n",
    "            第一个字符串从 i1 开始，第二个字符串从 i2 开始，子串的长度为 length，是否和谐\n",
    "            \"\"\"\n",
    "\n",
    "            # 判断两个子串是否相等\n",
    "            if s1[i1:i1+length] == s2[i2:i2+length]:\n",
    "                return True\n",
    "            \n",
    "            # 判断是否存在字符 c 在两个子串中出现的次数不同\n",
    "            if Counter(s1[i1:i1+length]) != Counter(s2[i2:i2+length]):\n",
    "                return False\n",
    "            \n",
    "            # 枚举分割位置\n",
    "            for i in range(1, length):\n",
    "                # 不交换的情况\n",
    "                if dfs(i1, i2, i) and dfs(i1 + i, i2 + i, length - i):\n",
    "                    return True\n",
    "                # 交换的情况\n",
    "                if dfs(i1, i2 + length - i, i) and dfs(i1 + i, i2, length - i):\n",
    "                    return True\n",
    "        \n",
    "            return False\n",
    "\n",
    "        ans = dfs(0, 0, len(s1))\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        @cache\n",
    "        def dfs(i, j, m):\n",
    "            if s1[i:i+m] == s2[j:j+m]:\n",
    "                return True\n",
    "            if Counter(s1[i:i+m]) != Counter(s2[j:j+m]):\n",
    "                return False\n",
    "            for k in range(1, m):\n",
    "                if dfs(i, j, k) and dfs(i+k, j+k, m-k):\n",
    "                    return True\n",
    "                if dfs(i,j+m-k,k) and dfs(i+k, j, m-k):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(0, 0, len(s1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if sorted(s1) != sorted(s2):\n",
    "            return False\n",
    "\n",
    "        memo = {}\n",
    "        def woo(s1, s2):\n",
    "            if (s1, s2) in memo:\n",
    "                return memo[(s1, s2)]\n",
    "\n",
    "            if s1 == s2:\n",
    "                return True\n",
    "\n",
    "            memo[(s1, s2)] = False\n",
    "            if sorted(s1) != sorted(s2):\n",
    "                return False\n",
    "                \n",
    "            for i in range(1, len(s1)):\n",
    "                if woo(s1[:i], s2[:i]) and woo(s1[i:], s2[i:]) or woo(s1[:i], s2[-i:]) and woo(s1[i:], s2[:-i]):\n",
    "                    memo[(s1, s2)] = True\n",
    "                    return True\n",
    "\n",
    "            return memo[(s1, s2)]\n",
    "\n",
    "        return woo(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        @cache\n",
    "        def sep(x1, x2):\n",
    "            if Counter(x1) != Counter(x2):\n",
    "                return False\n",
    "            if x1 == x2:\n",
    "                return True\n",
    "            for k in range(1, len(x1)):\n",
    "                if (sep(x1[:k], x2[:k]) and sep(x1[k:], x2[k:])) or (sep(x1[:k], x2[-k:]) and sep(x1[k:], x2[:-k])):\n",
    "                    return True\n",
    "            return False\n",
    "            \n",
    "        return sep(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if len(s1) != len(s2):\n",
    "            return False\n",
    "\n",
    "        if sorted(s1) != sorted(s2):\n",
    "            return False\n",
    "\n",
    "        memo = {}\n",
    "        def woo(s1, s2):\n",
    "            if (s1, s2) in memo:\n",
    "                return memo[(s1, s2)]\n",
    "\n",
    "            if s1 == s2:\n",
    "                return True\n",
    "\n",
    "            memo[(s1, s2)] = False\n",
    "            if sorted(s1) != sorted(s2):\n",
    "                return False\n",
    "\n",
    "            for i in range(1, len(s1)):\n",
    "                if woo(s1[:i], s2[:i]) and woo(s1[i:], s2[i:]) or woo(s1[:i], s2[-i:]) and woo(s1[i:], s2[:-i]):\n",
    "                    memo[(s1, s2)] = True\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return woo(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        l1, l2 = len(s1), len(s2)\n",
    "        if l1 == 0 or l2 == 0 or l1 != l2: return False\n",
    "\n",
    "        @lru_cache(maxsize = None)\n",
    "        def is_true(a, b):\n",
    "            # assume a and b have the same length and > 0\n",
    "            #print(a, b)\n",
    "            l = len(a)\n",
    "            if l == 1: return a == b\n",
    "            if sorted(a) != sorted(b): return False\n",
    "            flag = False\n",
    "            for i in range(1, l):\n",
    "                flag = is_true(a[:i], b[:i]) and is_true(a[i:], b[i:])\n",
    "                if flag: return True\n",
    "                flag = is_true(a[:i], b[l - i:]) and is_true(a[i:], b[:l - i])\n",
    "                if flag: return True\n",
    "            return flag\n",
    "        \n",
    "        return is_true(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        memo = {}\n",
    "\n",
    "        def helper(s1, s2):\n",
    "            if (s1, s2) in memo:\n",
    "                return memo[(s1, s2)]\n",
    "\n",
    "            # 判断 s1 和 s2 是否相等\n",
    "            if s1 == s2:\n",
    "                memo[(s1, s2)] = True\n",
    "                return True\n",
    "\n",
    "            # 判断两个字符串是否包含相同的字符\n",
    "            if sorted(s1) != sorted(s2):\n",
    "                memo[(s1, s2)] = False\n",
    "                return False\n",
    "\n",
    "            # 尝试分割字符串并比较两种情况\n",
    "            for i in range(1, len(s1)):\n",
    "                if (helper(s1[:i], s2[:i]) and helper(s1[i:], s2[i:])) or \\\n",
    "                   (helper(s1[:i], s2[-i:]) and helper(s1[i:], s2[:-i])):\n",
    "                    memo[(s1, s2)] = True\n",
    "                    return True\n",
    "\n",
    "            memo[(s1, s2)] = False\n",
    "            return False\n",
    "\n",
    "        return helper(s1, s2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        wordDict = collections.defaultdict(int)\n",
    "        for ch in s1:\n",
    "            wordDict[ch] += 1\n",
    "        for ch in s2:\n",
    "            wordDict[ch] -= 1\n",
    "\n",
    "        for word in wordDict:\n",
    "            if wordDict[word] != 0:\n",
    "                return False\n",
    "\n",
    "        self.dp = {}\n",
    "        return self.isTarget(s1, s2)\n",
    "\n",
    "    def isTarget(self, s1, target):\n",
    "        if (s1, target) in self.dp:\n",
    "            return self.dp[(s1, target)]\n",
    "\n",
    "        if len(s1) == 1:\n",
    "            self.dp[(s1, target)] = s1 == target\n",
    "            return self.dp[(s1, target)] \n",
    "\n",
    "        if len(s1) == 2:\n",
    "            self.dp[(s1, target)] = s1 == target or s1[::-1] == target\n",
    "            return self.dp[(s1, target)] \n",
    "\n",
    "        if s1 == target:\n",
    "            self.dp[(s1, target)] = True\n",
    "            return True\n",
    "\n",
    "        for i in range(1, len(s1)):\n",
    "            left = s1[:i]\n",
    "            right = s1[i:]\n",
    "\n",
    "            leftTarget = target[:i]\n",
    "            rightTarget = target[i:]\n",
    "\n",
    "            if self.isTarget(left, leftTarget) and self.isTarget(right, rightTarget):\n",
    "                self.dp[(s1, target)] = True\n",
    "                return True\n",
    "\n",
    "            left, right = right, left\n",
    "            leftTarget = target[:len(left)]\n",
    "            rightTarget = target[len(left):]\n",
    "            if self.isTarget(left, leftTarget) and self.isTarget(right, rightTarget):\n",
    "                self.dp[(s1, target)] = True\n",
    "                return True\n",
    "        self.dp[(s1, target)] = False\n",
    "        return False\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        @cache\n",
    "        def search(i1, i2, length):\n",
    "            if s1[i1:i1+length] == s2[i2:i2+length]:\n",
    "                return True\n",
    "            if length == 1:\n",
    "                return False\n",
    "            for l in range(1, length):\n",
    "                if search(i1, i2+length-l, l) and search(i1+l, i2, length-l):\n",
    "                    return True\n",
    "                if search(i1, i2, l) and search(i1+l, i2+l, length-l):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return search(0, 0, len(s1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        import functools\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def solve(p, q, l):\n",
    "            if l == 1:\n",
    "                return s1[p] == s2[q]\n",
    "            for i in range(1, l):\n",
    "                if solve(p, q, i) and solve(p + i, q + i, l - i):\n",
    "                    return True\n",
    "                if solve(p, q + l - i, i) and solve(p + i, q, l - i):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return solve(0, 0, len(s1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        @cache\n",
    "        def dfs(i,j, a,b):\n",
    "            # is s2[i,j] scrumble string of s1[a,b]\n",
    "            if i > j:\n",
    "                return True\n",
    "            elif i == j:\n",
    "                return s1[a] == s2[i]\n",
    "\n",
    "            # [i,k] [k,j] for k in i+1...j-1\n",
    "            for l in range(1,j-i+1): # len of first partition\n",
    "                k1, k2 = i+l-1, a+l-1\n",
    "                if dfs(i, k1, a, k2) and dfs(k1+1, j, k2+1, b):\n",
    "                    return True\n",
    "                k1, k2 = i+l-1, b-l+1\n",
    "                if dfs(i, k1, k2, b) and dfs(k1+1, j, a, k2-1):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(0,len(s1)-1, 0,len(s1)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        ## dp[i][j] 表示字符串s1通过扰动是否可以得到s2\n",
    "        ## 返回dp[0][n-1]即可\n",
    "        n = len(s1)\n",
    "        # dp = [[False] * n for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     dp[i][i] == s1[i] == s2[i]\n",
    "        \n",
    "        ## 递推顺序从下向上\n",
    "        @cache\n",
    "        def dfs(s1i, s1j, s2i, s2j):\n",
    "            if s1i == s1j:\n",
    "                return s1[s1i]== s2[s2i]\n",
    "\n",
    "            flag = False\n",
    "            length = s1j - s1i\n",
    "            i = 0\n",
    "            while not flag and i < length:\n",
    "                flag |= (dfs(s1i, s1i + i, s2i, s2i + i ) and dfs(s1i + i + 1, s1j, s2i + i + 1, s2j))\n",
    "                flag |= (dfs(s1i, s1i + i, s2j - i, s2j) and dfs(s1i + i + 1, s1j, s2i, s2j - i - 1))\n",
    "\n",
    "                i += 1 \n",
    "\n",
    "            return flag            \n",
    "        \n",
    "\n",
    "        return dfs(0, n-1, 0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        N = len(s1)\n",
    "        if N == 0: return True\n",
    "        if N == 1: return s1 == s2\n",
    "        if sorted(s1) != sorted(s2):\n",
    "            return False\n",
    "        for i in range(1, N):\n",
    "            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):\n",
    "                return True\n",
    "            elif self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "        if len(s1) != len(s2):\n",
    "            return False\n",
    "        if s1 == s2:\n",
    "            return True\n",
    "        if sorted(s1) != sorted(s2): # 有字母不一样，通过扰乱不能达成一致\n",
    "            return False\n",
    "\n",
    "        # 遍历切割点\n",
    "        for i in range(1, len(s1)):\n",
    "\n",
    "            # 情况一、分隔之后的两段不交换，递归看字集是否可以通过扰乱达成一致\n",
    "            a = self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:])\n",
    "        \n",
    "            # 情况二、分隔之后的两段要交换(s1的前半段和s2的后半段比较扰乱)\n",
    "            b = self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i])\n",
    "\n",
    "            if a or b:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @functools.lru_cache(None)\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        N = len(s1)\n",
    "        if N == 0: return True\n",
    "        if N == 1: return s1 == s2\n",
    "        if sorted(s1) != sorted(s2):\n",
    "            return False\n",
    "        for i in range(1, N):\n",
    "            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):\n",
    "                return True\n",
    "            elif self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @functools.lru_cache(None)\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        N = len(s1)\n",
    "        if N == 0: return True\n",
    "        if N == 1: return s1 == s2\n",
    "        if sorted(s1) != sorted(s2):\n",
    "            return False\n",
    "        for i in range(1, N):\n",
    "            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):\n",
    "                return True\n",
    "            elif self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        if n == 0:\n",
    "            return True\n",
    "        if n == 1:\n",
    "            return s1 == s2\n",
    "        if sorted(s1) != sorted(s2):\n",
    "            return False\n",
    "        for i in range(1,n):\n",
    "            if self.isScramble(s1[i:],s2[i:]) and self.isScramble(s1[:i],s2[:i]):\n",
    "                return True\n",
    "            elif self.isScramble(s1[i:],s2[:-i]) and self.isScramble(s1[:i],s2[-i:]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        if n == 0:\n",
    "            return True\n",
    "        if n == 1:\n",
    "            return s1 == s2\n",
    "        if sorted(s1) != sorted(s2):\n",
    "            return False\n",
    "        for i in range(1,n):\n",
    "            if self.isScramble(s1[i:],s2[i:]) and self.isScramble(s1[:i],s2[:i]):\n",
    "                return True\n",
    "            elif self.isScramble(s1[i:],s2[:-i]) and self.isScramble(s1[:i],s2[-i:]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        d = dict()\n",
    "        def recur(s1,s2):\n",
    "            n = len(s1)\n",
    "            if n==1:\n",
    "                if s1 == s2:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            if s1+s2 in d:\n",
    "                return d[s1+s2]\n",
    "            for i in range(1,n):\n",
    "                al = s1[:i]\n",
    "                ar = s1[i:]\n",
    "\n",
    "                bl = s2[:i]\n",
    "                br = s2[i:]\n",
    "\n",
    "                cl = s2[:-i]\n",
    "                cr = s2[-i:]\n",
    "\n",
    "                if recur(al,bl) and recur(ar,br):\n",
    "                    d[s1+s2] = True\n",
    "                    return True\n",
    "\n",
    "                if recur(al,cr) and recur(ar,cl):\n",
    "                    d[s1+s2] = True\n",
    "                    return True\n",
    "            d[s1+s2] = False\n",
    "            return False\n",
    "\n",
    "        return recur(s1,s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(cur:str, target: str):\n",
    "\n",
    "            if cur == target:\n",
    "                return True\n",
    "\n",
    "            if len(cur) == 1 :\n",
    "                return cur == target\n",
    "\n",
    "            if len(cur) == 2:\n",
    "                return cur == target or (cur[0] == target[1] and cur[1] == target[0])\n",
    "\n",
    "            for i in range(1, len(cur)):\n",
    "                ret = (dfs(cur[:i], target[:i]) and dfs(cur[i:], target[i:])) or (dfs(cur[:i], target[-i:]) and dfs(cur[i:], target[:len(target) - i]))\n",
    "                if ret:\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(s1, s2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, s1, s2):\n",
    "        if len(s1) != len(s2):\n",
    "            return False\n",
    "        n = len(s1)\n",
    "        l1 = [0 for _ in range(26)]\n",
    "        l2 = [0 for _ in range(26)]\n",
    "        for i in range(n):\n",
    "            l1[ord(s1[i]) - 97] += 1\n",
    "            l2[ord(s2[i]) - 97] += 1\n",
    "        for i in range(26):\n",
    "            if l1[i] != l2[i]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if s1 == s2:\n",
    "            return True\n",
    "        if not self.check(s1, s2):\n",
    "            return False\n",
    "        n = len(s1)\n",
    "        N = -1\n",
    "        Y = 1\n",
    "        Empty = 0\n",
    "        dp = [[[0 for _ in range(n+1)] for _ in range(n)] for _ in range(n)]\n",
    "        def DFS(i, j, length):\n",
    "            if dp[i][j][length] != 0:\n",
    "                return dp[i][j][length] == Y\n",
    "            a = s1[i:i+length]\n",
    "            b = s2[j:j+length]\n",
    "            if a == b:\n",
    "                dp[i][j][length] = Y\n",
    "                return True\n",
    "            if not self.check(a, b):\n",
    "                dp[i][j][length] = N\n",
    "                return False    \n",
    "            for k in range(1, length):\n",
    "                if DFS(i,j,k) and DFS(i+k, j+k, length-k):\n",
    "                    dp[i][j][length] = Y\n",
    "                    return True\n",
    "                if DFS(i, j+length-k, k) and DFS(i+k, j, length-k):\n",
    "                    dp[i][j][length] = Y\n",
    "                    return True\n",
    "            dp[i][j][length] = n\n",
    "            return False\n",
    "        return DFS(0, 0, n)\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if sorted(s1) != sorted(s2):\n",
    "            return False\n",
    "\n",
    "        memo = {}\n",
    "\n",
    "        def woo(s1, s2):\n",
    "            if (s1, s2) in memo:\n",
    "                return memo[(s1, s2)]\n",
    "\n",
    "            if s1 == s2:\n",
    "                return True\n",
    "\n",
    "            memo[(s1, s2)] = False\n",
    "            for i in range(1, len(s1)):\n",
    "                if woo(s1[:i], s2[:i]) and woo(s1[i:], s2[i:]) or woo(s1[:i], s2[-i:]) and woo(s1[i:], s2[:-i]):\n",
    "                    memo[(s1, s2)] = True\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return woo(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        @cache\n",
    "        def scramble(s1, s2):\n",
    "            if len(s1) <= 1 and s1 == s2:\n",
    "                return True\n",
    "            for i in range(1, len(s1)):\n",
    "                if scramble(s1[:i], s2[:i]) and scramble(s1[i:], s2[i:]):\n",
    "                    return True\n",
    "                if scramble(s1[:i], s2[len(s1) - i:]) and scramble(s1[i:], s2[:len(s1) - i]):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return scramble(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        @cache\n",
    "        def dfs(s1: str, s2: str) -> bool:\n",
    "            n = len(s1)\n",
    "            if n == 1:\n",
    "                return s1 == s2\n",
    "            for i in range(1, n):\n",
    "                if dfs(s1[:i], s2[:i]) and dfs(s1[i:], s2[i:]) or dfs(s1[:i], s2[n-i:]) and dfs(s1[i:], s2[:n-i]):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        @cache\n",
    "        def dfs(s, t):\n",
    "            n = len(s)\n",
    "            if s == t:\n",
    "                return True\n",
    "            elif n == 1:\n",
    "                return False\n",
    "            for i in range(1, n):\n",
    "                if dfs(s[:i], t[:i]) and dfs(s[i:], t[i:]) or dfs(s[i:], t[:n - i]) and dfs(s[:i], t[n - i:]):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return dfs(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        @cache\n",
    "        def f(i, j, k):\n",
    "            if s1[i:i+k] == s2[j:j+k]:\n",
    "                return True\n",
    "            if Counter(s1) != Counter(s2):\n",
    "                return False\n",
    "            for l in range(1, k):\n",
    "                if f(i, j, l) and f(i+l, j+l, k-l):\n",
    "                    return True\n",
    "            for l in range(1, k):\n",
    "                if f(i, j+k-l, l) and f(i+l, j, k-l):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return f(0, 0, len(s1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        def f(l1, l2, lens):\n",
    "            if lens == 1:\n",
    "                return s1[l1] == s2[l2]\n",
    "            if dp[l1][l2][lens] != 0:\n",
    "                return dp[l1][l2][lens] == 1\n",
    "            ans = False\n",
    "            for k in range(1, lens):\n",
    "                if f(l1, l2, k) and f(l1+k, l2+k, lens-k):\n",
    "                    ans = True\n",
    "                    break\n",
    "            if not ans:\n",
    "                i = l1 + 1\n",
    "                j = lens + l2 - 1\n",
    "                for k in range(1, lens):\n",
    "                    if f(l1, j, k) and f(i, l2, lens-k):\n",
    "                        ans = True\n",
    "                        break\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "            dp[l1][l2][lens] = 1 if ans else -1\n",
    "            return ans\n",
    "        n = len(s1)\n",
    "        dp = [[[0]*(n+1) for _ in range(n)] for _ in range(n)]\n",
    "        return f(0, 0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        def f(l1, l2, lens):\n",
    "            if lens == 1:\n",
    "                return s1[l1] == s2[l2]\n",
    "            if dp[l1][l2][lens] != 0:\n",
    "                return dp[l1][l2][lens] == 1\n",
    "            ans = False\n",
    "            for k in range(1, lens):\n",
    "                if f(l1, l2, k) and f(l1+k, l2+k, lens-k):\n",
    "                    ans = True\n",
    "                    break\n",
    "            if not ans:\n",
    "                i = l1 + 1\n",
    "                j = lens + l2 - 1\n",
    "                for k in range(1, lens):\n",
    "                    if f(l1, j, k) and f(i, l2, lens-k):\n",
    "                        ans = True\n",
    "                        break\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "            dp[l1][l2][lens] = 1 if ans else -1\n",
    "            return ans\n",
    "        n = len(s1)\n",
    "        dp = [[[0]*(n+1) for _ in range(n)] for _ in range(n)]\n",
    "        return f(0, 0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        memo = [[[0] * (n+1) for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        def dp(i, j, l):\n",
    "            if l == 1:\n",
    "                return s1[i] == s2[j]\n",
    "            if memo[i][j][l]:\n",
    "                return memo[i][j][l] == 1\n",
    "            result = False\n",
    "            for s in range(1, l):\n",
    "                if dp(i, j, s) and dp(i+s, j+s, l-s) or dp(i, j+l-s, s) and dp(i+s, j, l-s):\n",
    "                    result = True\n",
    "                    break\n",
    "            memo[i][j][l] = 1 if result else 2\n",
    "            return result\n",
    "        \n",
    "        return dp(0, 0, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "\n",
    "        if s1 == s2:\n",
    "            return True\n",
    "        if sorted(s1) != sorted(s2):\n",
    "            return False\n",
    "\n",
    "        for i in range(1,n):\n",
    "            x1, y1 = s1[:i], s1[i:]\n",
    "            flag1 = self.isScramble(x1,s2[:i])\n",
    "            flag2 = self.isScramble(y1,s2[i:])\n",
    "            flag3 = self.isScramble(x1,s2[n-i:])\n",
    "            flag4 = self.isScramble(y1,s2[:n-i])\n",
    "\n",
    "            if (flag1 and flag2) or (flag3 and flag4):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    map = {}\n",
    "\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        if len(s2) != n:\n",
    "            return False\n",
    "        if s1 == s2:\n",
    "            return True\n",
    "        if n == 1:\n",
    "            return False\n",
    "\n",
    "        key = s1 + \" \" + s2\n",
    "\n",
    "        if key in self.map:\n",
    "            return self.map[key]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            without_swap = self.isScramble(s1[:i], s2[:i]) and self.isScramble(\n",
    "                s1[i:], s2[i:]\n",
    "            )\n",
    "            if without_swap:\n",
    "                return True\n",
    "            with_swap = self.isScramble(s1[:i], s2[n - i :]) and self.isScramble(\n",
    "                s1[i:], s2[: n - i]\n",
    "            )\n",
    "            if with_swap:\n",
    "                return True\n",
    "\n",
    "        self.map[key] = False\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        # 递归版本 + 记忆化\n",
    "        # 时间复杂度O（n4）\n",
    "        # 空间复杂度O（n3）\n",
    "        if len(s1) != len(s2): return False\n",
    "        n = len(s1)\n",
    "        memo = [[[-1] * (n + 1) for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, j, length):\n",
    "            if memo[i][j][length] != -1: return memo[i][j][length]\n",
    "            sub_s1 = s1[i: i + length]\n",
    "            sub_s2 = s2[j: j + length]\n",
    "            if sub_s1 == sub_s2: \n",
    "                memo[i][j][length] = True\n",
    "                return memo[i][j][length]\n",
    "            if sorted(sub_s1) != sorted(sub_s2):\n",
    "                memo[i][j][length] = False\n",
    "                return memo[i][j][length]\n",
    "\n",
    "            for k in range(1, length):\n",
    "                if dfs(i, j, k) and dfs(i + k, j + k, length - k):\n",
    "                    memo[i][j][length] = True\n",
    "                    return memo[i][j][length]\n",
    "                if dfs(i, j + length - k, k) and dfs(i + k, j, length - k):\n",
    "                    memo[i][j][length] = True\n",
    "                    return memo[i][j][length]\n",
    "            return False\n",
    "        return dfs(0, 0, n)            \n",
    "\n",
    "\n",
    "\n",
    "        # # 动态规划\n",
    "        # # 时间复杂度O（n4）\n",
    "        # # 空间复杂度O（n3）\n",
    "        # if len(s1) != len(s2): return False\n",
    "        # n = len(s1)\n",
    "        # # 三维数组\n",
    "        # dp = [[[False] * (n + 1) for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         dp[i][j][1] = s1[i] == s2[j]\n",
    "\n",
    "        # for length in range(2, n + 1):\n",
    "        #     for i in range(n - length + 1):\n",
    "        #         for j in range(n - length + 1):\n",
    "        #             for k in range(1, length):\n",
    "        #                 if dp[i][j][k] and dp[i + k][j + k][length - k]:\n",
    "        #                     dp[i][j][length] = True\n",
    "        #                     continue\n",
    "        #                 if dp[i][j + length - k][k] and dp[i + k][j][length - k]:\n",
    "        #                     dp[i][j][length] = True\n",
    "        #                     continue\n",
    "\n",
    "        # return dp[0][0][n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    @lru_cache(None)\n",
    "    def isScramble(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if s1 == s2:\n",
    "            return True\n",
    "        if len(s1) != len(s2):\n",
    "            return False\n",
    "\n",
    "        for i in range(1, len(s1)):\n",
    "            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):\n",
    "                return True\n",
    "            if self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    re={}\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if s1 in self.re:\n",
    "            if s2 in self.re[s1]:\n",
    "                return self.re[s1][s2]\n",
    "        else:\n",
    "            self.re[s1]={}\n",
    "        if s1==s2:\n",
    "            return True\n",
    "        for x in range(1,len(s1)):\n",
    "            if self.isScramble(s1[:x],s2[:x]) and self.isScramble(s1[x:],s2[x:]):\n",
    "                self.re[s1][s2]=True\n",
    "                return True\n",
    "            if self.isScramble(s1[:x],s2[-x:]) and self.isScramble(s1[x:],s2[:len(s1)-x]):\n",
    "                self.re[s1][s2]=True\n",
    "                return True\n",
    "        self.re[s1][s2]=False\n",
    "        return False\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if s1 == s2: return True \n",
    "        if len(s1) != len(s2): return False \n",
    "        if sorted(s1) != sorted(s2): return False\n",
    "\n",
    "        for i in range(1, len(s1)):\n",
    "            left = self.isScramble(s1[:i],s2[:i])\n",
    "            right = self.isScramble(s1[i:],s2[i:])\n",
    "            if left and right: return True \n",
    "\n",
    "            left = self.isScramble(s1[:i],s2[-i:])\n",
    "            right = self.isScramble(s1[i:],s2[:-i])\n",
    "            if left and right: return True \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        slen=len(s1)\n",
    "        dps1=[[[0]*26 for _ in range(slen)] for _ in range(slen)]\n",
    "        dps2=[[[0]*26 for _ in range(slen)] for _ in range(slen)]\n",
    "        for row in range(slen):\n",
    "            for col in range(row,slen):\n",
    "                if row==0 and col==0:\n",
    "                    dps1[0][0][ord(s1[col])-ord(\"a\")]+=1\n",
    "                    dps2[0][0][ord(s2[col])-ord(\"a\")]+=1\n",
    "                else:\n",
    "                    dps1[row][col]=dps1[row][col-1][:]\n",
    "                    dps1[row][col][ord(s1[col])-ord(\"a\")]+=1\n",
    "                    dps2[row][col]=dps2[row][col-1][:]\n",
    "                    dps2[row][col][ord(s2[col])-ord(\"a\")]+=1\n",
    "        @functools.lru_cache(None)\n",
    "        def backtrack(start1,end1,start2,end2):\n",
    "            if s1[start1:end1+1]==s2[start2:end2+1]:\n",
    "                return True\n",
    "            for offset in range(0,end1-start1):\n",
    "                if dps1[start1][start1+offset]==dps2[start2][start2+offset]:\n",
    "                    res=backtrack(start1,start1+offset,start2,start2+offset) and backtrack(start1+offset+1,end1,start2+offset+1,end2)\n",
    "                    if res==True:\n",
    "                        return True\n",
    "                if dps1[start1][start1+offset]==dps2[end2-offset][end2]:\n",
    "                    res=backtrack(start1,start1+offset,end2-offset,end2) and backtrack(start1+offset+1,end1,start2,end2-offset-1)\n",
    "                    if res==True:\n",
    "                        return True\n",
    "            return False\n",
    "        if dps1[0][slen-1]!=dps2[0][slen-1]:\n",
    "            return False\n",
    "        return backtrack(0,slen-1,0,slen-1)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        def lookup(l1, r1, l2, r2):\n",
    "            key = '{},{},{},{}'.format(l1, r1, l2, r2)\n",
    "            if not key in mem:\n",
    "                mem[key] = dfs(l1, r1, l2, r2)\n",
    "            return mem[key]\n",
    "\n",
    "        def dfs(l1, r1, l2, r2):\n",
    "            assert (r1 - l1) == (r2 - l2)\n",
    "            n = r1 - l1\n",
    "            if n == 1:\n",
    "                return s1[l1] == s2[l2]\n",
    "            rst = False\n",
    "            for length in range(1, n):\n",
    "                rst |= lookup(l1, l1 + length, l2, l2 + length) and lookup(l1 + length, r1, l2 + length, r2)\n",
    "                rst |= lookup(r1 - length, r1, l2, l2 + length) and lookup(l1, r1 - length, l2 + length, r2)\n",
    "            return rst\n",
    "        mem = {}\n",
    "        return dfs(0, len(s1), 0, len(s2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        \n",
    "        if s1 == s2: return True\n",
    "\n",
    "        n = len(s1)\n",
    "\n",
    "        return self.func(s1, s2, 0, 0, n)\n",
    "    @lru_cache(None)\n",
    "    def func(self, s1, s2, l1, l2, size):\n",
    "        if size == 1:\n",
    "            return s1[l1] == s2[l2]\n",
    "        for part in range(1, size):\n",
    "            if (self.func(s1, s2, l1, l2, part) and self.func(s1, s2, l1 + part, l2 + part, size - part)) or (self.func(s1, s2, l1, l2 + size - part, part) and self.func(s1, s2, l1 + part, l2, size - part)):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        return self.dp(s1, s2, 0, len(s1), 0, len(s2))\n",
    "    @cache\n",
    "    def dp(self,s1,s2, l1,r1,l2,r2):\n",
    "        if s1[l1:r1] == s2[l2:r2]:\n",
    "            return True\n",
    "        elif r1-l1 < 3:\n",
    "            set1 = set(s1[l1:r1])\n",
    "            set2 = set(s2[l2:r2])\n",
    "            print(set1, set2)\n",
    "            return set1 == set2\n",
    "        for mid in range(l1+1, r1):\n",
    "            lenl = mid - l1\n",
    "            midr = l2 + lenl\n",
    "            if self.dp(s1,s2,l1, mid, l2,midr) and \\\n",
    "            self.dp(s1,s2,mid,r1, midr,r2) or \\\n",
    "            self.dp(s1,s2,l1,mid, r2-lenl, r2) and \\\n",
    "            self.dp(s1,s2,mid,r1, l2, r2-lenl):\n",
    "                return True\n",
    "        return False\n",
    "            \n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool: \n",
    "\n",
    "        memo = {}\n",
    "        def dp1(s1, s2):\n",
    "            l1, l2 = len(s1), len(s2)\n",
    "            if l1 != l2 or l1 == 0:\n",
    "                return False\n",
    "            if l1 == 1:\n",
    "                if s1[0] == s2[0]:\n",
    "                    return True \n",
    "                else:\n",
    "                    return False\n",
    "            if (s1, s2) not in memo:\n",
    "                l = len(s1)\n",
    "                ans = False \n",
    "                for i in range(1, l):\n",
    "                    # print('-'*8)\n",
    "                    # print(s1[:i], s2[:i], s1[i:], s2[i:])\n",
    "                    # print(s1[:l-i], s2[i:], s1[l-i:], s2[:i])\n",
    "                    # a = dp1(s1[:i], s2[:i]) and dp1(s1[i:], s2[i:])\n",
    "                    # b = dp1(s1[:l-i], s2[i:]) and dp1(s1[i:], s2[:l-i])\n",
    "                    # print(a, b)\n",
    "                    ans = ans or (dp1(s1[:i], s2[:i]) and dp1(s1[i:], s2[i:]))\n",
    "                    ans = ans or (dp1(s1[:l-i], s2[i:]) and dp1(s1[l-i:], s2[:i]))\n",
    "                memo[s1, s2] = ans \n",
    "            return memo[s1, s2]\n",
    "                    \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        return dp1(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        n1, n2 = len(s1), len(s2)\n",
    "        if n1 != n2:\n",
    "            return False\n",
    "        i = 0\n",
    "        while i < n1 and s1[i] == s2[i]:\n",
    "            i += 1\n",
    "        if i == n1:\n",
    "            return True\n",
    "        for j in range(i+1, n1):\n",
    "            if (self.isScramble(s1[i:j], s2[n1-j+i:n1]) and self.isScramble(s1[j:n1], s2[i:n1-j+i])) or (self.isScramble(s1[i:j], s2[i:j]) and self.isScramble(s1[j:n1], s2[j:n1])):                \n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        @cache\n",
    "        def dfs(s1: str, s2: str) -> bool:\n",
    "            # print(s1, s2)\n",
    "            if s1 == s2: return True\n",
    "            n = len(s1)\n",
    "            if n == 1: return s1 == s2\n",
    "            for i in range(1, n):\n",
    "                x, y = s2[:i], s2[i:]\n",
    "                # s1_left, s1_right = s1[:i], s1[i:]\n",
    "                # print(s2, x, y, s1, s1_left, s1_right)\n",
    "                if (dfs(s1[:i], x) and dfs(s1[i:], y)) or (dfs(s1[:n - i], y) and dfs(s1[n - i:], x)): return True\n",
    "            return False\n",
    "        n = len(s1)\n",
    "        return dfs(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 有想法了。\n",
    "    # 1 把s1 s2的所有子字符串是否char组成相同统计出来，一共n*n的表，on2\n",
    "    # 2 对字符串寻找分割点，对每个分割点左右的字符串x1y1/x2y2比较是否可能是一次分割。若是，则对其子字符串也做这个判断。这是一个递归过程，但是最高复杂度on2。\n",
    "    # 实质二分思想，一定能过。\n",
    "    # 不过这个算法的两步倒都算是编程上的难点。\n",
    "\n",
    "    # pps: 这个思路挂了，还是用DP/记忆化搜索得了。\n",
    "    # 记忆化搜索是自上而下的DP。DP本身自下而上。\n",
    "    # 记忆化搜索的好处是 1:代码简洁，递归便于理解，利用率体系结构的根本机制。但是和DP没什么太大的差别，根本上使用的是“后序遍历”，也就是自底向上的。2: 因为转移公式是or型的，也就是说子树有一个成功即成功，因此可以大量减少无用计算/剪枝了。\n",
    "    # 也确实用DFS来做, 我原本的思想没有太大问题，就差一个哆嗦实际上。\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        self.s1 = s1\n",
    "        self.s2 = s2\n",
    "        n = len(s1)\n",
    "        return self.dfs(0, 0, n)\n",
    "    \n",
    "    @cache\n",
    "    def dfs(self, i1, i2, n): # 比较两个长度相等的字符串是否是 扰乱字符串。 n > 0\n",
    "        if n == 1: return self.s1[i1] == self.s2[i2]\n",
    "        for x in range(1, n):\n",
    "            if (self.dfs(i1, i2, x) and self.dfs(i1+x, i2+x, n-x)):\n",
    "                return True\n",
    "            elif(self.dfs(i1, i2 + n - x, x) and self.dfs(i1+x, i2, n-x)):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "        \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        def helper(i1, i2, length):\n",
    "            curVal = f\"{i1}.{i2}.{length}\"\n",
    "            if curVal in memoDict:\n",
    "                return memoDict[curVal]\n",
    "            if s1[i1:i1+length] == s2[i2:i2+length]:\n",
    "                return True\n",
    "            if sorted(s1[i1:i1+length]) != sorted(s2[i2:i2+length]):\n",
    "                memoDict[curVal] = False\n",
    "                return False\n",
    "            ans = False\n",
    "            for sublen in range(1, length):\n",
    "                ans |= helper(i1, i2, sublen) & helper(i1+sublen, i2+sublen, length-sublen)\n",
    "                ans |= helper(i1, i2+length-sublen,sublen) & helper(i1+sublen, i2, length-sublen)\n",
    "            memoDict[curVal] = ans\n",
    "            return ans\n",
    "\n",
    "        memoDict = dict()\n",
    "        if len(s1) != len(s2):\n",
    "            return False\n",
    "        return helper(0, 0, len(s1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        mem = [[[ 0 for i in range(30)] for i in range(30)]for i in range(30)]\n",
    "        def dfs(i1: int, i2: int, length: int) -> int:\n",
    "            \"\"\"\n",
    "            第一个字符串从 i1 开始，第二个字符串从 i2 开始，子串的长度为 length，是否和谐\n",
    "            \"\"\"\n",
    "\n",
    "            # 判断两个子串是否相等\n",
    "            if s1[i1:i1+length] == s2[i2:i2+length]:\n",
    "                return 1\n",
    "            \n",
    "            # 判断是否存在字符 c 在两个子串中出现的次数不同\n",
    "            if Counter(s1[i1:i1+length]) != Counter(s2[i2:i2+length]):\n",
    "                return -1\n",
    "            \n",
    "            # 枚举分割位置\n",
    "            for i in range(1, length):\n",
    "                # 不交换的情况\n",
    "                if mem[i1][i2][i] == 0 :\n",
    "                    mem[i1][i2][i] = dfs(i1, i2, i) \n",
    "                if mem[i1+i][i2+i][length-i] == 0:\n",
    "                    mem[i1+i][i2+i][length-i] = dfs(i1 + i, i2 + i, length - i)\n",
    "                if mem[i1][i2][i] == 1 and  mem[i1+i][i2+i][length-i] == 1:\n",
    "                    return 1\n",
    "                # 交换的情况\n",
    "                if mem[i1][i2+length-i][i] == 0 :\n",
    "                    mem[i1][i2+length-i][i] = dfs(i1, i2+length-i, i) \n",
    "                if mem[i1+i][i2][length-i] == 0:\n",
    "                    mem[i1+i][i2][length-i] = dfs(i1 + i, i2, length - i)\n",
    "                if mem[i1][i2+length-i][i] == 1 and mem[i1+i][i2][length-i] == 1:\n",
    "                    return 1       \n",
    "            return -1\n",
    "        ans = dfs(0, 0, len(s1))\n",
    "        return True if ans == 1 else False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        demo = [[[None for i in range(31)] for i in range(31)] for i in range(31)]\n",
    "        @cache\n",
    "        def dfs(i1: int, i2: int, length: int) -> bool:\n",
    "            if demo[i1][i2][length] != None:\n",
    "                return demo[i1][i2][length]\n",
    "            \"\"\"\n",
    "            第一个字符串从 i1 开始，第二个字符串从 i2 开始，子串的长度为 length，是否和谐\n",
    "            \"\"\"\n",
    "\n",
    "            # 判断两个子串是否相等\n",
    "            if s1[i1:i1+length] == s2[i2:i2+length]:\n",
    "                demo[i1][i2][length] = True\n",
    "                return True\n",
    "            \n",
    "            # 判断是否存在字符 c 在两个子串中出现的次数不同\n",
    "            if Counter(s1[i1:i1+length]) != Counter(s2[i2:i2+length]):\n",
    "                demo[i1][i2][length] = False\n",
    "                return False\n",
    "            \n",
    "            # 枚举分割位置\n",
    "            for i in range(1, length):\n",
    "                # 不交换的情况\n",
    "                if dfs(i1, i2, i) and dfs(i1 + i, i2 + i, length - i):\n",
    "                    demo[i1][i2][length] = True\n",
    "                    return True\n",
    "                # 交换的情况\n",
    "                if dfs(i1, i2 + length - i, i) and dfs(i1 + i, i2, length - i):\n",
    "                    demo[i1][i2][length] = True\n",
    "                    return True\n",
    "            demo[i1][i2][length] = False\n",
    "            return False\n",
    "\n",
    "        ans = dfs(0, 0, len(s1))\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def isScramble(self, s1: str, s2: str) -> bool:\n",
    "#         n1 = len(s1)\n",
    "#         n2 = len(s2)\n",
    "#         if n1 != n2:\n",
    "#             return False\n",
    "#         # dp[i][j][k] 表示 S1 以 i为开头， S2以j为开头，长度为k，可以变换得到，即为True\n",
    "#         dp = [[[False]*(n1+1) for i in range(n1)] for i in range(n1)]\n",
    "#         for i in range(n1):\n",
    "#             for j in range(n1):\n",
    "#                 if s1[i] == s2[j]:\n",
    "#                     dp[i][j][1] = True\n",
    "\n",
    "#         # 先划分长度区间,可以保证每次的长度都是相同\n",
    "#         for length in range(2, n1+1):\n",
    "#             for i in range(n1-length+1):\n",
    "#                 for j in range(n1-length+1):\n",
    "#                     for k in range(1, length):\n",
    "#                         #第一种情况：S1->T1,S2->T2\n",
    "#                         if dp[i][j][k] and dp[i+k][j+k][length-k]:\n",
    "#                             dp[i][j][length] = True\n",
    "#                         #第二种情况：S1->T2,S1->T2\n",
    "#                         elif dp[i][j+length-k][k] and dp[i+k][j][length-k]:\n",
    "#                             dp[i][j][length] = True\n",
    "#         return dp[0][0][n1]\n",
    "## 试试记忆化递归\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        memo = {}\n",
    "        def helper(s1, s2):\n",
    "            if (s1, s2) in memo:\n",
    "                return memo[(s1, s2)]\n",
    "            n = len(s1)\n",
    "            if n == 1:\n",
    "                return s1 == s2\n",
    "            for i in range(1, n):\n",
    "                if helper(s1[i:], s2[i:]) and helper(s1[:i], s2[:i]):\n",
    "                    memo[(s1, s2)] = True\n",
    "                    return True\n",
    "                elif helper(s1[:i], s2[-i:]) and helper(s1[i:], s2[:-i]):\n",
    "                    memo[(s1, s2)] = True\n",
    "                    return True\n",
    "            memo[(s1, s2)] = False\n",
    "            return False\n",
    "        return len(s1) == len(s2) and helper(s1, s2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        def helper(s1: str, s2: str):\n",
    "            key = s1 + '@' + s2\n",
    "            if key in self.dict:\n",
    "                return self.dict[key]\n",
    "            if s1 == s2:\n",
    "                self.dict[key] = True\n",
    "                return True\n",
    "            size = len(s1)\n",
    "            for i in range(1, size):\n",
    "                if helper(s1[:i], s2[:i]) and helper(s1[i:], s2[i:]):\n",
    "                    self.dict[key] = True\n",
    "                    return True\n",
    "                if helper(s1[:i], s2[::-1][:i]) and helper(s1[i:], s2[::-1][i:]):\n",
    "                    self.dict[key] = True\n",
    "                    return True\n",
    "            self.dict[key] = False\n",
    "            return False\n",
    "        \n",
    "        self.dict = {}\n",
    "        ans = helper(s1, s2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "def judge(s1, s2):\n",
    "  if (s1, s2) in mem:\n",
    "    return mem[s1, s2]\n",
    "  else:\n",
    "    if len(s1) == 1:\n",
    "      r = s1[0] == s2[0]\n",
    "    else:\n",
    "      r = False\n",
    "      for i in range(1, len(s1)):\n",
    "        if (judge(s1[:i], s2[:i]) and judge(s1[i:], s2[i:])) or (\n",
    "            judge(s1[:i], s2[-i:]) and judge(s1[i:], s2[:-i])):\n",
    "          r = True\n",
    "          break\n",
    "    mem[s1, s2] = r\n",
    "  return r\n",
    "\n",
    "\n",
    "mem = {}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "  def isScramble(self, s1: str, s2: str) -> bool:\n",
    "    return judge(s1, s2)\n",
    "    # stack = [s1]\n",
    "    # while len(stack) > 0:\n",
    "    #   s = stack.pop(0)\n",
    "    #   for i in range(1, len(s)):\n",
    "    #     stack.append((s1[:i], s2[:i]),(s1[i:], s2[i:])))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    memo = {}\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if s1 == s2:\n",
    "            return True\n",
    "        if (s1, s2) in self.memo:\n",
    "            return self.memo[(s1, s2)]\n",
    "        for i in range(1, len(s1)):\n",
    "            if (self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:])) or (self.isScramble(s1[:i], s2[len(s1)-i:]) and self.isScramble(s1[i:], s2[:len(s1)-i])):\n",
    "                self.memo[(s1, s2)] = True\n",
    "                return True\n",
    "        self.memo[(s1, s2)] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def helper(s1, s2):\n",
    "            if len(s1) == 1:\n",
    "                return s1[0] == s2[0]\n",
    "            \n",
    "            n = len(s1)\n",
    "            ans = False\n",
    "            for i in range(1, n):\n",
    "                ans1 = helper(s1[:i], s2[:i]) and helper(s1[i:], s2[i:])\n",
    "                ans2 = helper(s1[:i], s2[-i:]) and helper(s1[i:], s2[0:-i])\n",
    "                ans = ans | ans1 | ans2\n",
    "            return ans\n",
    "        \n",
    "        if len(s1) != len(s2):\n",
    "            return False\n",
    "        return helper(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if s1==s2:\n",
    "            return True\n",
    "        if len(s1)==1:\n",
    "            return s1==s2\n",
    "        if sorted(s1)!=sorted(s2):\n",
    "            return False\n",
    "        ans=False\n",
    "        for i in range(1,len(s1)):\n",
    "            s1First=s1[:i]\n",
    "            s1Last=s1[i:]\n",
    "            s2FirstA=s2[:i]\n",
    "            s2LastA=s2[i:]\n",
    "            j=len(s2)-i\n",
    "            s2FirstB=s2[:j]\n",
    "            s2LastB=s2[j:]\n",
    "            r1=self.isScramble(s1First,s2FirstA) and self.isScramble(s1Last,s2LastA)\n",
    "            r2=self.isScramble(s1First,s2LastB) and self.isScramble(s1Last,s2FirstB)\n",
    "            ans=ans or (r1 or r2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def isScramble(s1, s2):\n",
    "    if s1 == s2:\n",
    "        return True\n",
    "    if len(s1) == 1:\n",
    "        return False\n",
    "    for i in range(1, len(s1)):\n",
    "        if isScramble(s1[:i], s2[:i]) and isScramble(s1[i:], s2[i:]):\n",
    "            return True\n",
    "        if isScramble(s1[:i], s2[-i:]) and isScramble(s1[i:], s2[:-i]):\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if Counter(s1) != Counter(s2):\n",
    "            return False\n",
    "        \n",
    "        return isScramble(s1, s2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        return s1 == s2 or Counter(s1) == Counter(s2) and any([self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]) or self.isScramble(s1[i:], s2[:-i]) and self.isScramble(s1[:i], s2[-i:]) for i in range(1, len(s1))])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        d = {}\n",
    "        def check(l1,l2):\n",
    "            tk = tuple(sorted([l1,l2]))\n",
    "            if tk in d.keys():\n",
    "                return d[tk]\n",
    "            if l1 == l2:\n",
    "                d[tk] = True\n",
    "                return True\n",
    "            if len(l1) == 1:\n",
    "                d[tk] = l1 == l2\n",
    "                return l1 == l2\n",
    "            acc = 0\n",
    "            for i in range(1,len(l1)):\n",
    "                r1 = check(l1[:i],l2[:i]) and check(l1[i:],l2[i:])\n",
    "                r2 = check(l1[:i],l2[-i:]) and check(l1[i:],l2[:-i])\n",
    "                r = r1 or r2\n",
    "                acc += int(r)\n",
    "            d[tk] = acc>0\n",
    "            return acc > 0\n",
    "        return check(s1,s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @functools.cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if len(s1) == 1:\n",
    "            return s1 == s2\n",
    "        # if sorted(s1) != sorted(s2):\n",
    "        #     return False\n",
    "\n",
    "        for i in range(1, len(s1)):\n",
    "            left, right = s1[:i], s1[i:]\n",
    "            if self.isScramble(left, s2[:i]) and self.isScramble(right, s2[i:]):\n",
    "                return True\n",
    "            if self.isScramble(left, s2[-i:]) and self.isScramble(right, s2[:len(right)]):\n",
    "                return True\n",
    "\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 超时\n",
    "class Solution:\n",
    "    seen = set()\n",
    "    # @lru_cache(None) #一定要用这个cache 不然超时 用seen或者用cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if (s1, s2) in self.seen:\n",
    "            return False\n",
    "        if not s1 or not s2:\n",
    "            return not s1 and s2\n",
    "        # if collections.Counter(s1) != collections.Counter(s2):\n",
    "        #     return False\n",
    "        length = len(s1)\n",
    "        if s1 == s2 or s1 == s2[::-1]:\n",
    "            return True\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            if (self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:])) or \\\n",
    "                (self.isScramble(s1[:i], s2[length - i:]) and self.isScramble(s1[i:], s2[:length - i])):\n",
    "                return True\n",
    "        self.seen.add((s1, s2)) #或者这样 \n",
    "        return False\n",
    "\n",
    "# class Solution:\n",
    "#     def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if s1 == s2:\n",
    "            return True\n",
    "        \n",
    "        if collections.Counter(s1) != collections.Counter(s2):\n",
    "            return False\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(s1, s2):\n",
    "            # base\n",
    "            n = len(s1)\n",
    "            \n",
    "            if n == 1:\n",
    "                return s1 == s2\n",
    "            \n",
    "            # 不换\n",
    "            for i in range(1, n):\n",
    "                left_s1 = s1[:i]\n",
    "                right_s1 = s1[i:]\n",
    "                \n",
    "                left_s2 = s2[:i]\n",
    "                right_s2 = s2[i:]\n",
    "                \n",
    "                if dfs(left_s1, left_s2) and dfs(right_s1, right_s2):\n",
    "                    return True\n",
    "            \n",
    "            # 换\n",
    "            \n",
    "            for i in range(1, n):\n",
    "                left_s1 = s1[:i]\n",
    "                right_s1 = s1[i:]\n",
    "                \n",
    "                right_s2 = s2[-i:]\n",
    "                left_s2 = s2[:-i]\n",
    "                if dfs(left_s1, right_s2) and dfs(right_s1, left_s2):\n",
    "                    return True\n",
    "            \n",
    "            \n",
    "            return False\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        return dfs(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    @functools.lru_cache(None)\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if len(s1)!=len(s2):\n",
    "            return False\n",
    "        if s1 == s2:\n",
    "            return True\n",
    "        n = len(s1)\n",
    "        for i in range(1, len(s1)):\n",
    "            if self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):\n",
    "                return True\n",
    "            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        \n",
    "        if m != n:\n",
    "            return False\n",
    "        \n",
    "        @cache\n",
    "        def dfs(s1, s2):\n",
    "            if s1 == s2:\n",
    "                return True\n",
    "            m = len(s1)\n",
    "            \n",
    "            for i in range(1, m):\n",
    "                x1, y1 = s1[: i], s1[i: ]\n",
    "                x2, y2 = s2[: i], s2[i: ]\n",
    "                \n",
    "                if dfs(x1, x2) and dfs(y1, y2):\n",
    "                    return True\n",
    "                \n",
    "                x2, y2 = s2[: m - i], s2[m - i: ]\n",
    "                if dfs(x1, y2) and dfs(x2, y1):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        x1 = [c for c in s1]\n",
    "        x2 = [c for c in s2]\n",
    "        x1.sort()\n",
    "        x2.sort()\n",
    "        _n = len(x1)\n",
    "        for i in range(_n):\n",
    "            if x1[i] != x2[i]:\n",
    "                return False\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check(src, tar):\n",
    "            n = len(src)\n",
    "            if n == 1:\n",
    "                return src == tar\n",
    "            for i in range(1, n):\n",
    "                t0 = [c for c in src[:i]]\n",
    "                t1 = [c for c in tar[:i]]\n",
    "                for j in range(len(t0)):\n",
    "                    if t0[j] != t1[j]:\n",
    "                        continue\n",
    "                if check(src[:i], tar[:i]) and check(src[i:], tar[i:]):\n",
    "                    return True\n",
    "\n",
    "            for i in range(1, n):\n",
    "                t0 = [c for c in src[:i]]\n",
    "                t1 = [c for c in tar[-i:]]\n",
    "                for j in range(len(t0)):\n",
    "                    if t0[j] != t1[j]:\n",
    "                        continue\n",
    "                if check(src[:i], tar[-i:]) and check(src[i:], tar[:-i]):\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        ans = check(s1, s2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        if n == 1:\n",
    "            return s1 == s2\n",
    "        for i in range(1, n):\n",
    "            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):\n",
    "                return True\n",
    "            if self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):\n",
    "                return True\n",
    "        return False\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        if n == 1: return s1 == s2\n",
    "        for i in range(1, n):\n",
    "            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]): return True\n",
    "            if self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]): return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "@cache\n",
    "def func1(s1, s2):\n",
    "    if len(s1) == 1:\n",
    "        return s1 == s2\n",
    "\n",
    "    for i in range(1, len(s1)):\n",
    "        if func1(s1[:i], s2[:i]) and func1(s1[i:], s2[i:]):\n",
    "            return True\n",
    "        if func1(s1[:i], s2[-i:]) and func1(s1[i:], s2[:-i]):\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        return func1(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(x, y):\n",
    "    return x == y or any((dfs(x[:i], y[:i]) and dfs(x[i:], y[i:])) or (dfs(x[:i], y[-i:]) and dfs(x[i:], y[:-i])) for i in range(1, len(x)))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        return dfs(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        m = len(s1)\n",
    "        self.cache = [[[[None] * m for _ in range(m)] for _ in range(m)] for _ in range(m)]\n",
    "        return self.dfs(s1,s2,0,m-1,0,m-1)\n",
    "\n",
    "    def dfs(self, s1, s2, i1,j1,i2,j2):\n",
    "        if self.cache[i1][j1][i2][j2] != None:\n",
    "            return self.cache[i1][j1][i2][j2]\n",
    "        if Counter(s1[i1:j1+1]) != Counter(s2[i2:j2+1]):\n",
    "            self.cache[i1][j1][i2][j2] = False\n",
    "            return False\n",
    "        if s1[i1:j1+1] == s2[i2:j2+1]:\n",
    "            self.cache[i1][j1][i2][j2] = True\n",
    "            return True\n",
    "        for i in range(j1-i1):\n",
    "            if self.dfs(s1,s2,i1,i1+i,i2,i2+i) and self.dfs(s1,s2,i1+i+1,j1,i2+i+1,j2):\n",
    "                self.cache[i1][j1][i2][j2] = True\n",
    "                return True\n",
    "            if self.dfs(s1,s2,i1,i1+i,j2-i,j2) and self.dfs(s1,s2,i1+i+1,j1,i2,j2-i-1):\n",
    "                self.cache[i1][j1][i2][j2] = True\n",
    "                return True\n",
    "        self.cache[i1][j1][i2][j2] = False\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if s1 == s2:\n",
    "            return True\n",
    "        if len(s1) != len(s2):\n",
    "            return False\n",
    "        if len(s1) <= 1:\n",
    "            return False\n",
    "        for i in range(len(s1)-1):\n",
    "            if self.isScramble(s1[:i+1], s2[:i+1]) and self.isScramble(s1[i+1:], s2[i+1:]):\n",
    "                return True\n",
    "            if self.isScramble(s1[:i+1], s2[len(s1)-i-1:]) and self.isScramble(s1[i+1:], s2[:len(s1)-i-1]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        lenS = len(s1)\n",
    "        if(lenS == 1):\n",
    "            if(s1 == s2) :\n",
    "                return True # the  only one letter is the same, this means a match\n",
    "            if Counter(s1) != Counter(s2):\n",
    "                return False\n",
    "        for i in range(1,lenS):\n",
    "            if self.isScramble(s1[0:i],s2[0:i]) and self.isScramble(s1[i:lenS],s2[i:lenS]):\n",
    "                    return True # find a match when do NOT exchange\n",
    "            newS = s1[i:lenS] + s1[0:i] \n",
    "            if self.isScramble(newS[0:lenS - i],s2[0:lenS - i]) and self.isScramble(newS[lenS - i:lenS],s2[lenS - i:lenS]):\n",
    "                    return True # find a match when do exchangee\n",
    "        return False # do not find a match at the end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        if s1 == s2:\n",
    "            return True\n",
    "        m, n = len(s1), len(s2)\n",
    "        if m != n:\n",
    "            return False\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            s1Left = s1[: i]\n",
    "            s1Right = s1[i: ]\n",
    "            if self.isScramble(s1Left, s2[: i]) and self.isScramble(s1Right, s2[i: ]):\n",
    "                return True\n",
    "            if self.isScramble(s1Left, s2[m - i: ]) and self.isScramble(s1Right, s2[: m - i]):\n",
    "                return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        if n == 1:return s1==s2\n",
    "        for i in range(1,n):\n",
    "            if self.isScramble(s1[:i],s2[:i]) and self.isScramble(s1[i:],s2[i:]):return True\n",
    "            if self.isScramble(s1[:i],s2[-i:]) and self.isScramble(s1[i:],s2[:-i]):return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        if n == 1:return s1==s2\n",
    "        for i in range(1,n):\n",
    "            if self.isScramble(s1[:i],s2[:i]) and self.isScramble(s1[i:],s2[i:]):return True\n",
    "            if self.isScramble(s1[:i],s2[-i:]) and self.isScramble(s1[i:],s2[:-i]):return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        l1 = len(s1)\n",
    "        l2 = len(s2)\n",
    "\n",
    "        if l1 != l2: return False\n",
    "        if l1 == 1: return s1 == s2\n",
    "\n",
    "        for i in range(1, l1):\n",
    "            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):\n",
    "                return True\n",
    "            if self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        l1 = len(s1)\n",
    "        l2 = len(s2)\n",
    "\n",
    "        if l1 != l2: return False\n",
    "        if l1 == 1: return s1 == s2\n",
    "\n",
    "        for i in range(1, l1):\n",
    "            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):\n",
    "                return True\n",
    "            if self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):\n",
    "                return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
